package com.lw.leetcode.back.c;

import java.util.HashMap;
import java.util.LinkedList;
import java.util.Map;

/**
 * Created with IntelliJ IDEA.
 * 854. 相似度为 K 的字符串
 *
 * @author liw
 * @version 1.0
 * @date 2022/9/21 9:11
 */
public class KSimilarity {

    public static void main(String[] args) {
        KSimilarity test = new KSimilarity();

        // 2
//        String str1 = "abc";
//        String str2 = "bca";

        // 2
//        String str1 = "ab";
//        String str2 = "ba";

        // 9
//        String str1 = "abccaacceecdeea";
//        String str2 = "bcaacceeccdeaae";

        // 12
        String str1 = "cdebcdeadedaaaebfbcf";
        String str2 = "baaddacfedebefdabecc";

        int i = test.kSimilarity(str1, str2);
        System.out.println(i);
    }

    public int kSimilarity(String s1, String s2) {
        if (s1.equals(s2)) {
            return 0;
        }
        Map<Long, Integer> map = new HashMap<>();
        int length = s1.length();
        long n1 = toNum(s1);
        long n2 = toNum(s2);
        map.put(n1, 0);
        LinkedList<Long> list = new LinkedList<>();
        list.add(n1);
        int count = 0;
        while (!list.isEmpty()) {
            long value = list.pollFirst();
            int v = map.get(value);
            int index = (v & 31);
            count = (v >> 5) + 1;
            for (int i = index; i < length; i++) {
                long af = (value >> (i * 3)) & 7L;
                long pfi = (n2 >> (i * 3)) & 7L;
                if (af == pfi) {
                    continue;
                }
                long a = af << (i * 3);
                for (int j = i + 1; j < length; j++) {
                    long bf = (value >> (j * 3)) & 7L;
                    long b = bf << (j * 3);
                    long pf = (n2 >> (j * 3)) & 7L;
                    if (bf == pf || bf != pfi) {
                        continue;
                    }
                    long a1 = a << ((j - i) * 3);
                    long b1 = b >> ((j - i) * 3);
                    long t = value - a - b + a1 + b1;
                    if (t == n2) {
                        return count;
                    }
                    if (map.containsKey(t)) {
                        continue;
                    }
                    map.put(t, (count << 5) + i);
                    list.addLast(t);
                }
                break;
            }
        }
        return count;
    }

    private long toNum(String str) {
        int length = str.length();
        long item = 0;
        for (int i = 0; i < length; i++) {
            item += (((long) (str.charAt(i) - 'a')) << (3 * i));
        }
        return item;
    }

}
